# A bloody large number.
from loa_game import EMPTY, WHITE, SpinAction, MoveAction, Direction, BLACK
from utilities.quads import Quads
from utilities.centerOfMass import CenterOfMass
from utilities.frame_penalty import FramePenaltyUtil
from time import clock
INFINITY = 1.0e400
TIME = 0
FINISH = 1
CACHE = 2

class ModifiedAlphaBetaSearch:
    
    DEBUG = False
    '''
    This search algorithm implements the limited-resource minimax tree search 
    algorithm with alpha-beta pruning for zero-sum games. This version cuts off 
    search by depth alone and uses an evaluation function (utility).
    '''
    roots_dictionary = dict()
    leaves_dictionary = dict()
    root_cache_hit = 0
    root_cache_miss = 0
    leaves_cache_hit = 0
    leaves_cache_miss = 0
    turn_time_limit = 0
    
    quadsWeight = 3
    frameWeight = 10
    distWeight  = 4
    
    def __init__(self, player, max_depth, turn_time_limit, whiteCom = None, blackCom = None, wQuads = None, bQuads = None):
        '''
        Constructor.
        
        @param player: Your player. This search algorithm will choose the best
                       actions for this player.
        @param max_depth: The depth of the search tree.
        @param whiteCom: center of mass object for the white player
        @param blackCom: center of mass object for the black player 
        @param wQuads: quads object for the white player
        @param bQuads: quads object for the black player
        '''
        self.player     = player
        self.max_depth  = max_depth

        #center of mass
        self.whiteCom   = whiteCom
        self.blackCom   = blackCom 
        #White player Quads
        self.wQuads     = wQuads   
        #Black player Quads
        self.bQuads     = bQuads
        ModifiedAlphaBetaSearch.turn_time_limit = 0.95*turn_time_limit
    
    def utility(self, state, ancestor):
        '''
        Utility function
        '''
       
        
        if state.getCurrentPlayer() == WHITE:
            eulerNumber     = self.wQuads.eulerNumber()
            distFromCOM     = self.whiteCom.sumOfDistancesFromCOM(state)
        else:
            eulerNumber     = self.bQuads.eulerNumber()
            distFromCOM     = self.blackCom.sumOfDistancesFromCOM(state)
        
        #when euler number is <= 1 there is a winner with high probability
        eulerNumber2 = 10/eulerNumber
        winner =  state.getWinner()
        if winner == self.player:
            return INFINITY
        elif winner == self.get_opponent_player():
            return -INFINITY
        
        distFromCOM     = ((-1)*ModifiedAlphaBetaSearch.distWeight*distFromCOM)
        eulerNumber     = ((-1)*ModifiedAlphaBetaSearch.quadsWeight*eulerNumber)
        framePenalty    = FramePenaltyUtil(state.getCurrentPlayer()).utility(state, ancestor)
        framePenalty    = ((-1)*ModifiedAlphaBetaSearch.frameWeight*framePenalty)
#        print eulerNumber + distFromCOM + framePenalty
        return eulerNumber + distFromCOM + framePenalty + eulerNumber2
    
    def get_opponent_player(self):
        if self.player == WHITE:
            return BLACK
        return WHITE
    
    def search_anytime(self, root_state, is_first_run):
        '''
        Just like search, but supports multiple calls in the same turn - ANYTIME
        '''
        if is_first_run:
            self.time_start = clock()
        return self.search(root_state)
            
    def search(self, root_state):
        '''
        Search game to determine best action; use alpha-beta pruning.
        
        @param current_state: The current game state to start the search from.
        '''
        
        self.bQuads = Quads(root_state.size, root_state.board, BLACK)
        self.wQuads = Quads(root_state.size, root_state.board, WHITE)
        self.whiteCom = CenterOfMass(WHITE, root_state.size, root_state.board, False)
        self.blackCom = CenterOfMass(BLACK, root_state.size, root_state.board, False)
        best_value = -INFINITY
        best_action = None
        if self.DEBUG:
            print "********Search State********"
            print root_state
            print "****************************"
        #Check if current state exists in the cache
        try:
            stored_value, stored_action = ModifiedAlphaBetaSearch.roots_dictionary[root_state, self.max_depth]
        except KeyError:
            stored_action = None
        if not stored_action is None:
            #current state appears in the cache - return the corresponding value
            ModifiedAlphaBetaSearch.root_cache_hit += 1
            return stored_value, stored_action, CACHE
        ModifiedAlphaBetaSearch.root_cache_miss += 1
        for action, state in root_state.getSuccessors().items():
            value_fn = self._getValueFn(state)
            value, reason = value_fn(state, -INFINITY, INFINITY, 1,root_state,\
                             self.whiteCom, self.blackCom,self.wQuads, self.bQuads)
            if value > best_value:
                best_value = value
                best_action = action
            if reason == TIME:
                if best_action is None:
                    return best_value, action, reason
                return best_value, best_action, reason
        ModifiedAlphaBetaSearch.roots_dictionary[root_state, self.max_depth] = best_value, best_action
        return best_value, best_action, reason
    
    def _getValueFn(self, state):
        if state.getCurrentPlayer() == self.player:
            return self._maxValue
        else:
            return self._minValue
    
    def _cutoffTest(self, state, depth):
        return depth >= self.max_depth or (not self.getWinner(state) is None)
    
    def _maxValue(self, state, alpha, beta, depth, ancestor, wCOM, bCOM, wQuads, bQuads):
        if self._cutoffTest(state, depth):
            try:
                stored_value = ModifiedAlphaBetaSearch.leaves_dictionary[state]
            except KeyError:
                stored_value = None
            if not stored_value is None:
                #cache hit
                ModifiedAlphaBetaSearch.leaves_cache_hit += 1
                return stored_value, CACHE
            else:
                #cache miss
                ModifiedAlphaBetaSearch.leaves_cache_miss += 1
                new_value = self.utility(state, ancestor)
                ModifiedAlphaBetaSearch.leaves_dictionary[state] = new_value
                return new_value, FINISH
        ###########DEBUG###########
        if self.DEBUG:
            print "Depth: ", depth
        ###########################
        value = -INFINITY
        for action, successor in state.getSuccessors().items():
            if clock()-self.time_start > ModifiedAlphaBetaSearch.turn_time_limit:
                    return value, TIME
            #copy data to local variables
            localWcom   = wCOM.clone()
            localBcom   = bCOM.clone()
            localWquads = wQuads.clone()
            localBquads = bQuads.clone()
            self.updateUtilityData(state, successor, action, state.getCurrentPlayer(), localWquads, localBquads, localWcom, localBcom)
            value_fn = self._getValueFn(successor)
            returned_value, reason = value_fn(successor, alpha, beta, depth + 1, state, localWcom, localBcom, localWquads, localBquads)
            value = max(value, returned_value)
            if reason == TIME:
                return value, reason
            if value >= beta:
                return value, reason
            alpha = max(alpha, value)
        
        return value, reason
    
    def _minValue(self, state, alpha, beta, depth, ancestor, wCOM, bCOM, wQuads, bQuads):
        if self._cutoffTest(state, depth):
            try:
                stored_value = ModifiedAlphaBetaSearch.leaves_dictionary[state]
            except KeyError:
                stored_value = None
            if not stored_value is None:
                #cache hit
                ModifiedAlphaBetaSearch.leaves_cache_hit += 1
                return stored_value, CACHE
            else:
                #cache miss
                ModifiedAlphaBetaSearch.leaves_cache_miss += 1
                new_value = self.utility(state, ancestor)
                ModifiedAlphaBetaSearch.leaves_dictionary[state] = new_value
                return new_value, FINISH
        
        value = INFINITY
        for action, successor in state.getSuccessors().items():
            if clock()-self.time_start > ModifiedAlphaBetaSearch.turn_time_limit:
                    return value, TIME
            #copy data to local variables
            localWcom   = wCOM.clone()
            localBcom   = bCOM.clone()
            localWquads = wQuads.clone()
            localBquads = bQuads.clone()
            self.updateUtilityData(state, successor, action, state.getCurrentPlayer(), localWquads, localBquads, localWcom, localBcom)
            value_fn = self._getValueFn(successor)
            returned_value, reason = value_fn(successor, alpha, beta, depth + 1, state, localWcom, localBcom, localWquads, localBquads)
            value = min(value, returned_value)
            if reason == TIME:
                return value, reason
            if value <= alpha:
                return value, reason
            beta = min(beta, value)
        
        return value, reason
    
    def updateUtilityData(self, state, successor, action, player, \
                            whiteQ, blackQ, whiteCOM, blackCOM):
        '''
        update all utility data after action is applied to the board
        @param state: state before the move is applied
        @param successor: state after the move is applied
        @param action: action such that: Action(state) = successor
        @param player: player who made the move
        @param whiteQ: white player quads object
        @param blackQ: black player quads object
        @param whiteCOM: white player center of mass object
        @param blackCOM: black player center of mass object
        '''
        if isinstance(action, MoveAction):
            #Move Action!    
            results = self.getPositionsAfterMove(state, successor, action)
            ###########DEBUG###########
            if self.DEBUG:
                print action
                print ":::UpdateUtilData:: Playre: ", player ," old pos: ", results[0], " new pos: ", results[1]
                print "Current State"
                print state
                print "=============="
                print "Succesor"
                print successor
            ###########################
            if player == WHITE:
                self.updateDataAfterMove(results[0], results[1], whiteQ, whiteCOM)
                #if player has eaten one of the opponents piece
                if results[2]:
                    self.updateEatPiece(results[1], blackQ, blackCOM)
            else:
                self.updateDataAfterMove(results[0], results[1], blackQ, blackCOM)
                #if player has eaten one of the opponents piece
                if results[2]:
                    self.updateEatPiece(results[1], whiteQ, whiteCOM)
        else:
            #Spin Action
            self.updateDataAfterSpin((action.row, action.col), whiteQ, whiteCOM, WHITE, successor.board)
            self.updateDataAfterSpin((action.row, action.col), blackQ, blackCOM, BLACK, successor.board)
    
    def updateEatPiece(self, point, quad, com):
        '''
        make the updates to the objects after a piece has been eaten at a specific point
        @param quad: quad object
        @param centerOfMass: center of mass object
        '''
        quad.removePiece(point)
        com.eatPiece(point)
    
    def updateDataAfterMove(self, oldPos, newPos, quads, com):
        '''
        update objects after a piece has been moved from oldPos to newPos
        
        @param oldPos: old position of the piece
        @param newPos: new position of the piece
        @param quads: the quads object to be changed
        @param com: the center of mass object to be changed
        '''
        quads.changeQuads(oldPos, newPos)
        com.changeCenter(oldPos, newPos)
        
    def updateDataAfterSpin(self, rootPos, quads, com, player, board):
        '''
        update objects after a spin move has been at {rootPos}
        
        @param rootPos: the point where the spin has been made
        @param quads: the quads object to be changed
        @param com: the center of mass object to be changed
        @param player: the player who's object wer'e changing
        @param board: current board state (after the spin) 
        '''
        #update quads
        quads.spin(rootPos, board, player)
        #change the center of mass
        
        #lowerLeft -> upperLeft
        if board[rootPos[0]][rootPos[1]] == player:
            newPos = (rootPos[0]    , rootPos[1])       #upperLeft
            oldPos = (rootPos[0] + 1, rootPos[1])   #upperRight
            com.changeCenter(oldPos, newPos)
        #upperLeft -> upperRight
        if board[rootPos[0]][rootPos[1] + 1] == player:
            newPos = (rootPos[0], rootPos[1] + 1)
            oldPos = (rootPos[0], rootPos[1])
            com.changeCenter(oldPos, newPos)
        #upperRight -> lowerRight
        if board[rootPos[0] + 1][rootPos[1] + 1] == player:
            newPos = (rootPos[0] + 1, rootPos[1] + 1)
            oldPos = (rootPos[0]    , rootPos[1] + 1)
            com.changeCenter(oldPos, newPos)
        #lowerRight -> lowerLeft 
        if board[rootPos[0] + 1][rootPos[1]] == player:
            newPos = (rootPos[0] + 1, rootPos[1])
            oldPos = (rootPos[0] + 1, rootPos[1] + 1)
            com.changeCenter(oldPos, newPos)
            
    def getPositionsAfterMove(self, state, successor, action):
        '''
        Calculate the old and new position of a piece after *action* is applied on the state
        @param state: current state
        @param successor: state after *action* is applied
        @param action: action object
        @return: (oldPos, newPos, eaten?) 
        '''
        oldPos  = (action.row, action.col)
        pos     = (action.row, action.col)
        count   = 0
        #count the number of pieces on the piece line
        while self.inBoard(pos, state.size):
            if state.board[pos[0]][pos[1]] != EMPTY:
                count += 1
            pos = action.direction.move(pos)
        
        pos = (action.row, action.col)
        #get opposite direction
        opposite_direction = Direction('temp', (-action.direction.delta[0], -action.direction.delta[1]))
        pos = opposite_direction.move(pos)
        while self.inBoard(pos, state.size):
            if state.board[pos[0]][pos[1]] != EMPTY:
                count += 1
            pos = opposite_direction.move(pos)
        
        #get new piece position
        newPos = oldPos
        for i in xrange(0, count):
            newPos = action.direction.move(newPos)
        
        #check if the the opponent lost a piece after the move
        eaten = False
        if state.board[newPos[0]][newPos[1]] != EMPTY:
            eaten = True
        
        ###########DEBUG###########
        if self.DEBUG:
            print "Count: ", count
            print "OLD: ", state.board[newPos[0]][newPos[1]], "NEW: ", successor.board[newPos[0]][newPos[1]]
            print "--Reults, New: ", newPos, " Old: ", oldPos, " Eaten: ", eaten
        ###########################
        return (oldPos, newPos, eaten)
        
    def inBoard(self, point, size):
        '''
        @param point: point which we want to check
        @param size: size of the board  
        @return: True iff point is in the board 
        '''
        return point[0] >= 0 and point[0] < size and \
               point[1] >= 0 and point[1] < size
    
    def getWinner(self, state):
        '''
        check if state has a winner
        @param state: 
        '''
        isWhite = True
        isBlack = True
        #if euler number <= 1 then there *might* be a winner in the sate 
        if self.wQuads.eulerNumber() > 1:
            isWhite = False
        if self.bQuads.eulerNumber() > 1:
            isBlack = False
        #if at least one is True - there might be a winner in the state
        if isWhite or isBlack:
            return state.getWinner()
        return None
        